/*
 * com.future CO.,ltd.
 */

package com.future;

/**
 * Description: 122. ������Ʊ�����ʱ�� II
 * ����һ���������� prices ������?prices[i] ��ʾĳ֧��Ʊ�� i ��ļ۸�
 * <p>
 * ��ÿһ�죬����Ծ����Ƿ����/����۹�Ʊ�������κ�ʱ��?���?ֻ�ܳ��� һ�� ��Ʊ����Ҳ�����ȹ���Ȼ���� ͬһ�� ���ۡ�
 * <p>
 * ���� ���ܻ�õ� ��� ����?��
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺prices = [7,1,5,3,6,4]
 * �����7
 * ���ͣ��ڵ� 2 �죨��Ʊ�۸� = 1����ʱ�����룬�ڵ� 3 �죨��Ʊ�۸� = 5����ʱ������, ��ʽ������ܻ������ = 5 - 1 = 4 ��
 * ?    ����ڵ� 4 �죨��Ʊ�۸� = 3����ʱ�����룬�ڵ� 5 �죨��Ʊ�۸� = 6����ʱ������, ��ʽ������ܻ������ = 6 - 3 = 3 ��
 * ������Ϊ 4 + 3 = 7 ��
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/5/3:11:14
 */
public class Solution_122 {

    /**
     * ˼·��
     * �ҵ������еĵ���Ƭ�Σ���¼����Ƭ�ε���Сֵ�����ֵ����ô��ÿ�εĵ���Ƭ�ε����ֵ-��Сֵ�ۼӺ;��Ǵ�
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int N = prices.length;
        int min = prices[0];
        int best = prices[0];
        int bestIncome = 0;
        for (int i = 1; i < N; i++) {
            if (prices[i] >= prices[i - 1]) {
                best = prices[i];
                if (i == N - 1) {
                    /**
                     * ������ǵ����ĳ��������һ����Ҫ����
                     * eg:{1,2,3,4,5}
                     */
                    bestIncome += best - min;
                }
            } else {
                bestIncome += best - min;
                min = prices[i];
                best = prices[i];
            }
        }
        return bestIncome;
    }
}
